#include <iostream>
#include <queue>
#include <functional>
#include <unordered_map>
using namespace std;


//快排分割函数
int partion(int arr[],int begin,int end) 
{
    int value = arr[begin];
    while (begin < end)
    {
        while (begin < end && arr[end] >= value)
        {
            end--;
        }
        if(begin < end) {
            arr[begin] = arr[end];
        } else {
            break;
        }
        while(begin < end && arr[begin] <= value) {
            begin++;
        }
        if(begin < end) {
            arr[end] = arr[begin];
        } else {
            break;
        }
    }
    arr[begin] = value;
    return begin;
    
}
void selectTopK(int arr[],int begin,int end,int k)
{
    int mid = partion(arr,begin,end);

    if(mid == k - 1) {
        return;
    } else if(mid > k - 1) {
        selectTopK(arr,begin,mid - 1,k);
    } else if(mid < k - 1) {
        selectTopK(arr,mid + 1,end,k);
    }
}
//快排分割解决topk
int main() 
{
    //求最小的三个元素
    int arr[] = {1,23,3,5,8,67,56,88,45,90,9};
    int size = sizeof arr / sizeof(arr[0]);

    int k = 3;
    selectTopK(arr,0,size - 1,k);

    for(int i = 0;i < k;i++) {
        cout << arr[i] << endl;
    }
}
#if x
//查重和topk综合起来
int main()
{
    std::vector<int> vec;
    for(int i = 0;i < 10000;i++) {
        vec.push_back(rand() % 1000);
    }
    //统计重复次数最小的前三个数字
    unordered_map<int,int> map;
    for(auto i : vec) {
        map[i]++;
    }
    //放入大根堆之前先设置好compare规则
    using Type = pair<int,int>;
    using Com = function<bool(Type&,Type&)>;
    priority_queue<Type,vector<Type>,Com> max_queue(
        [](Type& a,Type& b)->bool {
        return a.second > b.second;
    });

    auto it = map.begin();
    for(int i = 0;i < 3;i++) {
        max_queue.push(*it);
        it++;
    }
    for(;it != map.end();it++) {
        if(it->second > 1 && max_queue.top().second < it->second) {
            max_queue.push(*it);
        }
    }
    for(int i = 0 ;i < 3;i++) {
        std::cout <<"数字 ： "<<max_queue.top().first << " 重复次数 ："<< max_queue.top().second << endl;
        max_queue.pop();
    }
    //统计重复次数最多的前三个
}

//求序列中最大的三个元素
int main()
{
    std::vector<int> vec;
    for(int i = 0;i < 100;i++) {
        vec.push_back(rand() % 100);
    }
    //求最大的用小根堆，比堆顶还大的就入堆，比堆顶更小的就忽略。
    priority_queue<int,vector<int>,greater<int>> min_queue;
    min_queue.emplace(vec[0]);
    min_queue.emplace(vec[1]);
    min_queue.emplace(vec[2]);
    for(auto i = vec.begin() + 3;i != vec.end();i++) {
        if(min_queue.top() < *i) {
            min_queue.pop();
            min_queue.emplace(*i);
        } 
    }
    for(int i = 0 ;i < 3;i++) {
        std::cout << min_queue.top() << endl;
        min_queue.pop();
    }
}

//求出序列中值最小的前三个元素
int main()
{
    std::vector<int> vec;
    for(int i = 0;i < 100;i++) {
        vec.push_back(rand() % 100);
    }
    //求最小的用大根堆，比堆顶还小的就入堆，比堆顶大的就忽略。
    priority_queue<int> pri_queue;
    pri_queue.emplace(vec[0]);
    pri_queue.emplace(vec[1]);
    pri_queue.emplace(vec[2]);
    for(auto i = vec.begin() + 3;i != vec.end();i++) {
        if(pri_queue.top() > *i) {
            pri_queue.pop();
            pri_queue.emplace(*i);
        } 
    }
    for(int i = 0 ;i < 3;i++) {
        std::cout << pri_queue.top() << endl;
        pri_queue.pop();
    }
}
#endif